Now that we have initialized our MST set and populated the priority queue, the algorithm's core iterative process begins. At each step, we make the greedy choice: selecting the cheapest available edge that connects our existing tree to a new vertex.

  • First, we extract the minimum-weight edge from the priority queue. In this case, it's the edge $(A, C)$ with weight 3.
  • We then check if the destination vertex $C$ is already in our MST. Since it is not, we can safely add it.
  • The vertex $C$ is added to the set of visited nodes, and the edge $(A, C)$ is added to our final MST.
  • Finally, we update the frontier. We examine all of $C$'s neighbors ($B$, $D$, $E$) and add the new edges to the priority queue, which re-sorts itself.
Python: Prim's Algorithm - First Iteration
1import heapq
2
3graph = {
4    'A': {'B': 4, 'C': 3}, 'B': {'A': 4, 'C': 1, 'D': 5},
5    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6}, 'D': {'B': 5, 'C': 2, 'E': 8, 'F': 7},
6    'E': {'C': 6, 'D': 8, 'F': 9}, 'F': {'D': 7, 'E': 9}
7}
8# State from previous slide
9mst_vertices = {'A'}
10priority_queue = [(3, 'A', 'C'), (4, 'A', 'B')]
11mst_edges = []
12
13# Main loop - First iteration
14if priority_queue:
15    # 1. Make the greedy choice
16    weight, u, v = heapq.heappop(priority_queue)
17
18    # 2. Check if the new vertex is already in the MST
19    if v not in mst_vertices:
20        # 3. Add the new vertex and edge to our MST
21        mst_vertices.add(v)
22        mst_edges.append((u, v, weight))
23
24        # 4. Update the frontier with new edges
25        for neighbor, weight in graph[v].items():
26            if neighbor not in mst_vertices:
27                heapq.heappush(priority_queue, (weight, v, neighbor))